IJTCS 2021 | 会议接收论文（部分报告）介绍

IJTCS 北京大学前沿计算研究中心 2022-12-22

收录于合集 #IJTCS 2021 22个

编者按

第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办，图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。

本期带来“CSIAM 区块链”和“算法与复杂性”分论坛接收论文（部分报告）的精彩介绍。

“CSIAM区块链”接收论文报告议程

时间：2021年8月17日

时间	讲者	报告题目
11:00- 11:25	Xu Wang	Framework and algorithms for identifying honest blocks in blockchain

时间：2021年8月19日

时间	讲者	报告题目
19:00- 19:25	Yuncheng Qiao	Block-CES: Multi-institution collaborative credit evaluation system based on blockchain
19:30- 19:55	Zhengtang Fu	An intelligent electric vehicle charging system for new energy companies based on consortium blockchain

“CSIAM 区块链”接收论文报告介绍

Framework and algorithms for identifying honest blocks in blockchain

Xu Wang, Tsinghua University

Abstract

Blockchain technology gains more and more attention in the past decades and has been applied in many areas. The main bottleneck for the development and application of blockchain is its limited scalability. Blockchain with directed acyclic graph structure (BlockDAG) is proposed in order to alleviate the scalability problem. One of the key technical problems in BlockDAG is the identification of honest blocks which are very important for establishing a stable and invulnerable total order of all the blocks. The stability and security of BlockDAG largely depends on the precision of honest block identification. This paper presents a novel universal framework based on graph theory, called MaxCord, for identifying the honest blocks in BlockDAG. By introducing the concept of discord, the honest block identification is modelled as a generalized maximum independent set problem. Several algorithms are developed, including exact, greedy and iterative filtering algorithms. The extensive comparisons between proposed algorithms and the existing method were conducted on the simulated BlockDAG data to show that the proposed iterative filtering algorithm identifies the honest blocks both efficiently and effectively. The proposed MaxCord framework and algorithms can set the solid foundation for the BlockDAG technology.

Biography

Wang Xu received his Ph.D. degree in Operations Research and Cybernetics from Academy of Mathematics and Systems Science, Chinese Academy of Sciences, in 2020. Now he is a postdoctoral fellow in Department of Industrial Engineering, Tsinghua University. His research focuses on blockchain technology and operations research, and the optimization modeling in traffic.

Block-CES: Multi-institution collaborative credit evaluation system based on blockchain

Yuncheng Qiao, Hunan University

Abstract

Data sharing among different institutions can enhance the integrity of information, so as to evaluate the credit level of financing enterprises more accurately, but it also faces the problems of privacy leakage and data fraud. This paper proposes a credit evaluation system with secure sharing and multiparty collaborative computing based on blockchain. The system ensures the authenticity of data by the characteristics of irrevocability and traceability of blockchain. It simultaneously enables institutions to complete the construction of credit evaluation model without exposing their own data, and solves the privacy protection problem of collaborative computing among multiple institutions. The system consists of four modules: distributed ledger, access control, security aggregation and model storage. The distributed ledger module based on hyperledger fabric ensures the trusted storage of data. The access control module avoids unauthorized data access. The security aggregation module realizes the privacy of data transmission and collaborative computing process by elementary matrix transformation and 1-out-of-N oblivious transmission protocol, which makes it more consistent with the minimum principle of data transmission in GDPR and other regulations. Finally, a calculation case is given to show the detailed process of each participant building credit evaluation model by using security aggregation protocol. And the consistency of model parameters before and after privacy protection is verified.

Biography

Yuncheng Qiao is currently a Ph.D. candidate in management science and engineering, business school, Hunan University. His research interest lies in blockchian, privacy computation, credit evaluation, etc. He has applied for 2 patents, and published many papers in international journals and conferences such as ADV DIFFER EQU-NY, ACTA MATH APPL SIN-E, etc.

An intelligent electric vehicle charging system for new energy companies based on consortium blockchain

Zhengtang Fu, Beijing Institute of Technology

Abstract

With the concerns of environment protection, electric vehicle (EV) is regarded as a promising transportation tool for green cities project. Since the amount of EVs is rising shapely, the EV charging demands is also rapidly generated. However, seeking suitable charging facilities is not easy for EV users, new energy companies run charging stations separately for self-interests, and charging pile information is not transparent for drivers. This dilemma is not solved until the merging of blockchain technology. In this paper, a novel EV charging system is proposed for the cooperation of new energy companies and providing convenient charging services for users. In this system, charging information is managed and recorded by the company alliance based on consortium blockchain, which is tamper-resistant and multi-centralized. Meanwhile, a new smart contract is designed to balance the allocation of company' charging users, so that the profits of different new energy companies could be fairer. To equilibrate the interest of companies and EV users, a Bio-Objective Mixed-Integer Programming model (BOMILP) is proposed as the mathematical logic of smart contracts. Furthermore, we proposed a new algorithm named Limited Neighborhood Search with Memory (LNSM) to support the implementation of smart contracts, which could make the smart contract running faster and has a better performance. At last, the proposed EV charging system and the smart contract are validated through a real case study with the EV charging data in Beijing, China.

Biography

Zhengtang Fu is currently pursuing the Ph.D. degree with the Beijing Institute of Technology, Beijing, China. He received the master's degree from Shanghai Maritime University, Shanghai, China, in 2016. He owns plenty of working experience, including a consulting company, an European integration company, and a local intelligent manufacturing company. The latest working experience is Shanghai Inlaylink Internet of Things Technology Corporation as the Project Manager. He has published several papers related to simulation, algorithm, and data analysis. His research interests include the application of blockchain technology, the Internet of Things (IoT), and complex system.

“算法与复杂性”接收论文报告议程

时间：2021年8月18日

时间	讲者	报告题目
21:00- 21:25	Manolis Vasilakis	Faster Algorithms for k-SubsetSum and Variations
21:30- 21:55	Mingyang Gong	Improved approximation algorithms for multiprocessor scheduling with testing
22:00- 22:25	Yong Chen	Approximation algorithms for the directed path partition problems
22:30- 23:00	Liangde Tao	Hardness and Algorithms for Electoral Manipulation under Media Influence

“算法与复杂性”接收论文报告介绍

Faster Algorithms for k-SubsetSum and Variations

Manolis Vasilakis, National Technical University of Athens

Abstract

We present new, faster pseudopolynomial time algorithms for the -SubsetSum problem, defined as follows: given a set of positive integers and targets determine whether there exist disjoint subsets , such that , for .

Assuming is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm can solve the problem in time.

We build upon recent advances on SubsetSum due to Koiliaris and Xu [Koil19] and Bringmann [Brin17] in order to provide faster algorithms for -SubsetSum.

We devise two algorithms: a deterministic one of time complexity and a randomised one of complexity.

We further demonstrate how these algorithms can be used in order to cope with variations of -SubsetSum, namely SubsetSumRatio, -SubsetSumRatio and MultipleSubsetSum.

Biography

Manolis Vasilakis recently received the diploma in Electrical and Computer Engineering from the National Technical University of Athens with specialization in Computer Science. His interests lay in the field of theoretical computer science, and more specifically in approximation algorithms, subset sum/knapsack problems and fine grained complexity.

Improved approximation algorithms for multiprocessor scheduling with testing

Mingyang Gong, University of Alberta

Abstract

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem that has received numerous studies.

Scheduling with testing is an online variant where the processing time of a job is revealed by an extra test operation, or otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3:1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take a time unit. We propose to first sort the jobs into the non-increasing order of the ratio between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves improved competitive ratios, which approach 2:9513 when the number of machines tends to infinity in the general case; when all test operations take a time unit, our algorithm achieves even better competitive ratios approaching 2:8081.

Biography

Mingyang Gong is pursuing the Ph.D. in Department of Computer Science at University of Alberta. He received his Bachelor of Natural Sciences in Mathematics and Applied Mathematics in 2018 and Master in School of Mathematical Sciences in 2021 at Zhejiang University.

Approximation algorithms for the directed path partition problems

Yong Chen, Hangzhou Dianzi University

Abstract

Given a digraph G=(V,E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k>=3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When k>=7, we present an improved (k+2)/3-approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When k=3, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.

Biography

Yong Chen is currently an associate professor at the department of mathematics at Hangzhou Dianzi University. He received his Ph.D. in 2011 from the Department of Mathematics at Zhejiang University. He received his Bachelor's degree in 2005 from the Department of Mathematics at Hangzhou Dianzi University. Professor Chen's main research is the design of approximation algorithm for NP-hard combinatorial optimization problem under different models.

Hardness and Algorithms for Electoral Manipulation under Media Influence

Liangde Tao, Zhejiang University

Abstract

In this paper, we study a generalization of the classic bribery problem known as electoral manipulation under media influence (EMMI). This model is motivated by modern political campaigns where candidates try to convince voters through advertising in media (TV, newspaper, Internet). When compared with the classical bribery problem, the attacker in this setting cannot directly change opinions of individual voters, but instead can execute influences via a set of manipulation strategies (e.g., advertising on a TV channel). Different manipulation strategies incur different costs and influence different subsets of voters. Once receiving a significant amount of influence, a voter will change opinion. To characterize the opinion change of each voter, we adopt the well-accepted threshold model. We prove the NP-hardness of the EMMI problem and give a dynamic programming algorithm that runs in polynomial time for a restricted case of the EMMI problem.

Biography

Liangde Tao is a PhD student major in Computer Science at Zhejiang University. Previously, he obtained his B.E. from Zhejiang University (2012-2016). His research interests are broadly in optimization and approximation algorithms.

关于IJTCS

回顾 → 对话邓小铁：在首届IJTCS中，我看到了中国计算理论的成长

日程 → 推荐：大会特邀报告

日程 → 分论坛：算法博弈论

日程 → 分论坛：区块链技术

日程 → 分论坛：多智能体强化学习

日程 → 分论坛：机器学习理论

日程 → 分论坛：量子计算

日程 → 分论坛：人工智能与形式化方法

日程 → 分论坛：算法与复杂性

日程 → 分论坛：计算经济学

日程 → 分论坛：有意识的图灵机